package lc.q101_150;

import java.util.Arrays;

public class Q132 {

    public int minCut(String s) {
        boolean[][] per = new boolean[s.length()][s.length()];
        // 存储从i到j是否回文串
        for (int i = 0; i < s.length(); i++) {
            // 全部初始化为true
            Arrays.fill(per[i], true);
        }
        // （i，j)为回文当且仅当s[i]=s[j]而且s[i+1][j-1]是回文，i>j是都是回文
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.length(); j++) {
                per[i][j] = s.charAt(i) == s.charAt(j) && per[i + 1][j - 1];
            }
        }
        // 最小的分割点,表示0到i的最小分割点
        int[] minCuts = new int[s.length()];
        Arrays.fill(minCuts, Integer.MAX_VALUE);
        for (int i = 0; i < s.length(); i++) {
            if (per[0][i]) {
                minCuts[i] = 0;
            } else {
                // 寻找包含当前字符的回文串
                for (int j = 0; j < i; j++) {
                    if (per[j + 1][i]) {
                        // 如果是回文串
                        minCuts[i] = Integer.min(minCuts[i], minCuts[j] + 1);
                    }
                }
            }
        }
        return minCuts[s.length() - 1];
    }

    public static void main(String[] args) {
        Q132 q132 = new Q132();
        int aab = q132.minCut("aab");
    }

}
